package flare.vis.operator.filter
{
	import flare.animate.Transitioner;
	import flare.vis.data.Data;	
	import flare.vis.data.DataSprite;
	import flare.vis.data.EdgeSprite;
	import flare.vis.data.NodeSprite;
	import flare.vis.data.Tree;	
	import flare.vis.operator.Operator;

	/**
	 * Filter operator that computes a fisheye degree-of-interest function over
	 * a tree structure. Visibility and DOI (degree-of-interest) values are set
	 * for the nodes and edges in the structure. This function includes a set
	 * of focus nodes, and includes neighbors only in a limited window around
	 * these foci. The size of this window is determined by this operator's
	 * <code>distance</code> property. All ancestors of a focus up to the root
	 * of the tree are considered foci as well. By convention, DOI values start
	 * at zero for focus nodes, with decreasing negative numbers for each hop
	 * away from a focus. The DOI values computed by this filter are stored in
	 * the <code>DataSprite.props.doi</code> property.
	 * 
	 * <p>This form of filtering was described by George Furnas as early as 1981.
	 * For more information about Furnas' fisheye view calculation and DOI values,
	 * take a look at G.W. Furnas, "The FISHEYE View: A New Look at Structured 
	 * Files," Bell Laboratories Tech. Report, Murray Hill, New Jersey, 1981. 
	 * Available online at <a href="http://citeseer.nj.nec.com/furnas81fisheye.html">
	 * http://citeseer.nj.nec.com/furnas81fisheye.html</a>.</p>
	 */
	public class FisheyeTreeFilter extends Operator
	{
		/** An array of focal NodeSprites. */
		public var focusNodes:/*NodeSprite*/Array;
		/** Graph distance within within which items wll be visible. */
		public var distance:int;
		
		private var _divisor:Number;
		private var _root:NodeSprite;
		private var _t:Transitioner;
		
		/**
		 * Creates a new FisheyeTreeFilter
		 * @param focusNodes focusNodes an array of focal NodeSprites. Graph
		 *  distance is measured as the minimum number of edge-hops to one of
		 *  these nodes or their ancestors up to the root.
		 * @param distance graph distance within which items will be visible
		 */		
		public function FisheyeTreeFilter(focusNodes:Array=null,distance:int=1)
		{
			this.focusNodes = focusNodes;
			this.distance = distance;
		}
		
		/** @inheritDoc */
		public override function operate(t:Transitioner=null):void
		{
			_t = (t==null ? Transitioner.DEFAULT : t);
			var tree:Tree = visualization.tree;
			_divisor = tree.nodes.length;
        	_root = tree.root;
        
	        // mark the items
	        visualization.data.visit(function(ds:DataSprite):void {
	        	ds.props.doi = -Number.MAX_VALUE;
	        });
	        
	        // compute the fisheye over nodes
	        for each (var fn:NodeSprite in focusNodes) {
	        	visitFocus(fn, null);
	        }
	        visitFocus(_root, null);
	
	        // mark unreached items
	        visualization.data.visit(function(ds:DataSprite):void {
	        	if (ds.props.doi == -Number.MAX_VALUE)
	        		setVisibility(ds, false);
	        });
		}
		
		/**
		 * Set the visibility of a data sprite.
		 */
		private function setVisibility(ds:DataSprite, visible:Boolean):void
		{
			var alpha:Number = visible ? 1 : 0;
			var obj:Object = _t.$(ds);
				
			obj.alpha = alpha;
			if (ds is NodeSprite)
				(ds as NodeSprite).expanded = (ds.props.doi > -distance);
			if (_t.immediate) {
				ds.visible = visible;
			} else {
				obj.visible = visible;
			}
		}
		
		/**
	     * Visit a focus node.
	     */
	    private function visitFocus(n:NodeSprite, c:NodeSprite):void
	    {
	        if (n.props.doi <= -1 ) {
	            visit(n, c, 0, 0);
	            if (distance > 0) visitDescendants(n, c);
	            visitAncestors(n);
	        }
	    }
	    
	    /**
	     * Visit a specific node and update its degree-of-interest.
	     */
	    private function visit(n:NodeSprite, c:NodeSprite, doi:int, ldist:int):void
	    {
	    	setVisibility(n, true);
	        var localDOI:Number = -ldist / Math.min(1000.0, _divisor);
	        n.props.doi = doi + localDOI;
	        
	        if (c != null) {
	        	var e:EdgeSprite = c.parentEdge;
	        	e.props.doi = c.props.doi;
	        	setVisibility(e, true);
	        }
	    }
	    
	    /**
	     * Visit tree ancestors and their other descendants.
	     */
	    private function visitAncestors(n:NodeSprite):void
	    {
	        if (n == _root) return;
	        visitFocus(n.parentNode, n);
	    }
	    
	    /**
	     * Traverse tree descendents.
	     */
	    private function visitDescendants(p:NodeSprite, skip:NodeSprite):void
	    {
	    	var lidx:int = (skip == null ? 0 : skip.parentIndex);
	        
	        p.expanded = p.childDegree > 0;
	        for (var i:int=0; i<p.childDegree; ++i) {
	        	var c:NodeSprite = p.getChildNode(i);
	        	if (c == skip) continue;
	        	
	        	var doi:int = int(p.props.doi - 1);
	        	visit(c, c, doi, Math.abs(lidx-i));
	        	if (doi > -distance) visitDescendants(c, null);
	        }
	    }

		
	} // end of class FisheyeTreeFilter
}